A sample of 416 males from western and eastern Andalusia has been jointly analyzed for surnames and Y-chromosome haplogroups and haplotypes. The observed number of different surnames was 222 (353 when the second surname of the Spanish system of naming is considered). The great majority of recorded surnames have a Castilian-Leonese origin, while Catalan or Basque surnames have not been found. A few Arab-related surnames appear but none discernible of Sephardic-Jewish descent. Low correlation among surnames with different population frequencies and Y-chromosome markers, at different levels of genetic resolution, has been observed in Andalusia. This finding could be explained mainly by the very low rate of monophyletic surnames because of the historical process of surname ascription and the resulting high frequencies of the most common Spanish surnames. The introduction of surnames in Spain during the Middle Ages coincided with Reconquest of the territories under Islamic rule, and Muslims and Jews progressively adopted the present male line surname system. Sampled surnames and Y-chromosome lineages fit well a power-law distribution and observed isonymy is very close to that of the general population. Besides, our data and results show that the reliability of the isonymy method should be questioned because of the high rate of polyphyletic surnames, even in small geographic regions and autochthonous populations. Random isonymy would be consistently dependent of the most common surname frequencies in the population.